package com.lwg.datastructure.greedy;

/**
 * @author: lwg
 * @Date: 2022/2/20 18:01
 * @Description: 跳跃游戏
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * [3,2,1,0,4]
 * 分析：第一个数字是3  此时我们能最多跳到0这个位置，但是我们可以遍历这期间的位置
 * 即如果当前最大的跳跃数大于或等于当前位置的下标，则我们可以在此位置继续更新最大的跳跃数
 * 当我们在i=0 时 此时的最大跳跃数是3，则我们可以在 0-3 这些下标中不断地更新最大的跳跃数 ，因为在i=0时 最大跳跃数是3
 * 我们到达不了4 所以继续往下跳 ，范围在i=0~3 ,知道在此范围内 最大的跳跃数>i-1,即能达到最后一个位置，才算结束
 * (注：在第一步的时候 我们就开始更新当前位置的最大跳跃数，一直更新的最大跳跃数是当前位置+当前位置的数，如果一直遍历到从第一步开始
 * 所能到达的最大位数，仍然不能满足最大跳跃数>第一步的最大跳跃数，则表明我们到达不了最后一步)
 */
public class JumpGames {

    public boolean canJump(int[] nums) {
        int length = nums.length;
        int maxJump = 0;
        for (int i = 0; i < length; i++) {
            // 这两个步骤是初始化比较
            //当前位置的下标 小于或等于最大跳跃数 则说明可以继续往下跳  ，例如当i==1时 则是nums[1]=3  1<3
            if (i <= maxJump) {
                // 可以在当前范围内继续更新最大跳跃数，因为按上面的数组来算 在第一步是到达不了最后一位
                // 所以每次更新的最大跳跃数为 当前当前位置 +当前位置的数/第一步的最大跳跃数，如果最后最大跳跃数还是第一步的，说明也到达不了最后一位
                maxJump = Math.max(i + nums[i], maxJump);
            }
            if (maxJump >= length - 1) {
                return true;
            }
        }
        return false;
    }

    //跳跃游戏2

    /**
     * 分析： [2,3,1,1,4]
     * 通过更新最后的位置与数组的长度进行比较 当不小于时，说明跳到最后一个位置 或之后
     */
    public int canJump2(int[] nums) {
        // 1.得到数组的长度
        int length = nums.length;
        int step = 0;
        // 2.初始化数据
        int end = 1;
        // 3.每次更新记录开始的起点
        int start = 0;
        // 4.while循环判断最后的位置大小是否小于数组的长度
        while (end < length) {
            // 5. 得到当前最大的跳跃步数
            int maxStep = 0;
            for (int i = start; i < end; i++) {
                maxStep = Math.max(maxStep, i + nums[i]);
            }
            start = end;
            end = maxStep + 1;
            step++;
        }
        return step;
    }
}

class MainClass11 {
    public static int[] stringToIntegerArray(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return new int[0];
        }

        String[] parts = input.split(",");
        int[] output = new int[parts.length];
        for (int index = 0; index < parts.length; index++) {
            String part = parts[index].trim();
            output[index] = Integer.parseInt(part);
        }
        return output;
    }

    public static String booleanToString(boolean input) {
        return input ? "True" : "False";
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            int[] nums = stringToIntegerArray(line);

            boolean ret = new JumpGames().canJump(nums);

            String out = booleanToString(ret);

            System.out.print(out);
        }
    }
}
